package com.algorithm.note01Sort.entity;

public class BiteEntity {

    /**
     * 通过异或交换数组中两个下标的值【慎用】
     * 节约空间（减少变量定义）
     * 要求：交换位置的两个数内存空间中是两个不同的存储位置，否则会导致相同的数被置为 0！！！
     * @param arr
     * @param i
     * @param j
     */
    public void swapXOR(int[] arr, int i, int j) {
        // 通过 0 ^ N = N;  N^N=0; a ^ b = b ^ a; 推导出下面方案
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];// arr[j] = arr[i] ^ arr[j] ^ arr[j]
        arr[i] = arr[i] ^ arr[j];// arr[i] = arr[i] ^ arr[j] ^ arr[i]
    }

    /**
     * 通过位运算获取仅有一个数是奇数个的数组中对应的数
     * @param arr
     * @return
     */
    public int getODD(int[] arr){
        // 数组不满足要求处理
        if(arr == null){
            return -1;
        }else if(arr.length == 1){
            return arr[0];
        }

        // 获取数组第一位
        int tmp = arr[0];
        // 从第二问开始，异或运算整个数组
        for (int i = 1; i < arr.length; i++) {
            tmp = tmp ^ arr[i];
        }
        return tmp;
    }

    /**
     * 通过位运算获取仅有两个数是奇数个的数组中对应的数
     * @param arr
     * @return
     */
    public int[] getODDS(int[] arr){
        // 数组不满足要求处理
        if(arr == null ||arr.length == 1){
            return arr;
        }

        // 获取数组第一位
        int tmp = arr[0];
        // 从第二问开始，异或运算整个数组
        for (int i = 1; i < arr.length; i++) {
            tmp = tmp ^ arr[i];
        }

        // 取到最右边的1，这个1属于两个数之一
        // 取反+1再与上本身可以得到最右侧的1
        int rightOne = tmp & (~tmp + 1);
        int onlyOne = 0;

        for (int i = 0; i < arr.length; i++) {
            if( (arr[i] & rightOne) == rightOne){//与运算，获取所有在最右侧的位置上为1的数
                onlyOne = onlyOne ^ arr[i];//循环整个数组，异或运算导致偶数个的数在此不产生作用，只有奇数个的数会留下来
            }
        }

        return new int[]{onlyOne, onlyOne ^ tmp};
    }
}
